package 题目集.dfs.记忆化搜索;

import java.util.Arrays;
import java.util.Scanner;

/**
 * https://www.dotcpp.com/oj/contest6276_problem4.html
 */
public class 密码脱落 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        n = line.length();
        if (n <= 1) {
            System.out.println(0);
            return;
        }
        arr = new int[n];
        dp=new int[n][n];
        for (int[] ints : dp) {
            Arrays.fill(ints, -1);
        }
        for (int i = 0; i < n; i++) {
            arr[i] = line.charAt(i);
        }
        System.out.println(dfs(0, n - 1));
    }

    static int n;
    static int[] arr;
    static int[][] dp;

    public static int dfs(int i, int j) {
        if (dp[i][j] != -1) {
            return dp[i][j];
        }
        int lm = i + (j - i >> 1);
        int rm = i + (j - i + 1 >> 1);
        if (i == lm && j == rm) {   //双方抵达中点
            return arr[i] == arr[j] ? 0 : 1;
        }
        if (arr[i] != arr[j]) {
            dp[i][j]=Math.min(dfs(i + 1, j), dfs(i, j - 1)) + 1;  //在左侧添加一个和右侧一样的种子或者右侧添加一个和左侧一样的种子
            return dp[i][j];
        } else {
            dp[i][j]=dfs(i + 1, j - 1);  //左右两侧同时移动
            return dp[i][j];
        }
    }
}
